class Solution(object):
    def minimumEffortPath(self, heights):
        m = len(heights)
        n = len(heights[0])
        min_val = min([min([heights[i][j] for j in range(n)]) for i in range(m)])
        max_val = max([max([heights[i][j] for j in range(n)]) for i in range(m)])
        left = 0
        right = max_val - min_val
        used = [[0 for _ in range(n)] for _ in range(m)]

        def bfs(x, y, val, index):
            now = {(x, y)}
            used[x][y] = index
            while now:
                x, y = now.pop()
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]:
                    if 0 <= ux < m and 0 <= uy < n:
                        if used[ux][uy] != index and abs(heights[ux][uy] - heights[x][y]) <= val:
                            used[ux][uy] = index
                            if ux == m - 1 and uy == n - 1:
                                return True
                            now.add((ux, uy))
            return False

        index = 0
        while left < right:
            index += 1
            mid = (left + right) // 2
            if bfs(0, 0, mid, index):
                right = mid
            else:
                left = mid + 1
        return right
